package 寒假刷题;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class 最简分数 {
    public List<String> simplifiedFractions(int n) {
        List<String> list = new ArrayList<>();
        HashSet<Double> set = new HashSet<>();
        for (int i = 2; i <=n ; i++) {
            for (int j = 1; j < i; j++) {
              if (gcd(i,j)==1){
                  String s = j+"/"+i;
                  list.add(s);
              }
            }
        }
        return list;
    }
    int gcd(int a, int b) { // 欧几里得算法
        return b == 0 ? a : gcd(b, a % b);
    }
}
